Tại Côn Đảo, đầu tiên ông bị giam ở Banh (nhà lao), đây là trại giam lớn và cổ nhất ở Côn Đảo được thực dân Pháp xây dựng từ năm 1892. Tại nhà giam này, trong thời điểm đó còn có các đồng chí Lê Hồng Phong, Lê Duẩn, Tôn Đức Thắng, Phạm Hùng, Lê Đức Thọ, Ngô Gia Tự, Lê Văn Lương, Nguyễn Duy Trinh... Suốt 13 năm sống ở " địa ngục trần gian" người chiến sĩ cộng sản trẻ tuổi Võ Thúc Đồng luôn nêu tấm gương bất khuất, trung kiên một lòng theo Đảng. Bọn cai ngục coi ông là một trong những người tù "cứng đầu" nên đã dùng nhiều nhục hình tra tấn nhưng không khuất phục được người chiến sĩ cách mạng trẻ tuổi.

Tháng 8 năm 1945, Cách mạng Tháng Tám thành công, Côn Đảo được giải phóng. 5 giờ chiều ngày 22-9-1945, ông Võ Thúc Đồng cùng với gần 2.000 chiến sĩ cách mạng trở về đất liền.

Trở về đất liền, theo phân công của Đảng, ông liên tục đảm đương nhiều cương vị công tác quan trọng của Đảng ở nhiều địa phương phía Nam: Tỉnh ủy viên Tỉnh ủy Biên Hòa, Tỉnh ủy Phú Yên; Bí thư Tỉnh ủy Kon Tum (tháng 3 năm 1946).